﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace SharpSoft.Maths
{
    /// <summary>
    /// 多边形辅助工具
    /// </summary>
    public static class PolygonHelper
    {
        /// <summary>
        /// （耳切法）将多边形三角化(计算构成多边形的所有三角形的顶点顺序),约定多边形顶点顺序的方向为逆时针方向（笛卡尔/右手坐标系中）
        /// </summary>
        /// <returns>返回多边形三角化后的顶点顺序(包含重复顶点，后期按需优化)</returns>
        /// <remarks>
        /// <see cref="https://blog.csdn.net/u010019717/article/details/52753855"/>
        /// </remarks>
        public static List<System.Numerics.Vector2> Triangulate(System.Numerics.Vector2[] points)
        {
            List<System.Numerics.Vector2> ps = new List<System.Numerics.Vector2>(points);

            Func<int, bool> isEar = (index) =>
            {//判断是否为耳尖（该顶点所在的多边形内角<180°）
                var v1 = ps[index] - ps[index - 1];
                var v2 = ps[index + 1] - ps[index];

                var dg = VectorHelper.AngleBetween(v1, v2);
                return dg >= 0 && dg < MathF.PI;
            };

            Func<int, bool> hasInside = (index) =>
            {//测试是否存在任意点位于当前三角形中
                for (int i = 0; i < ps.Count; i++)
                {
                    if (i >= index - 1 && i <= index + 1) continue;
                    if (TrigonHelper.IsInsideTrigon(ps[index - 1], ps[index], ps[index + 1], ps[i])) return true;
                }

                return false;
            };
            List<int> inds = new List<int>(ps.Count * 3);
            List<Vector2> newpoints = new List<Vector2>(ps.Count * 3);
            bool canTriangulate = true;

            while (canTriangulate)
            {
                canTriangulate = false;
                for (int i = 0; i < ps.Count; i++)
                {
                    if (isEar(i) && !hasInside(i))
                    {
                        newpoints.Add(ps[i - 1]);
                        newpoints.Add(ps[i]);
                        newpoints.Add(ps[i + 1]);
                        ps.RemoveAt(i);
                        canTriangulate = true;//尚有符合要求的顶点  标记继续迭代查找
                    }
                }
            }
            return newpoints;
        }
        /// <summary>
        /// (回转数法)测试点是否包含在多边形内部
        /// </summary>
        /// <param name="points">闭合多边形</param>
        /// <param name="p"></param>
        /// <returns></returns>
        /// <remarks> 
        /// 当回转数为 0 时，点在闭合曲线外部。https://blog.csdn.net/Form_/article/details/77855163
        /// </remarks>
        public static bool IsInsidePolygon(Vector2[] points, Vector2 p)
        {
            double px = p.X,
                   py = p.Y;
            double sum = 0;

            for (int i = 0, length = points.Length, j = length - 1; i < length; j = i, i++)
            {
                double sx = points[i].X,
                    sy = points[i].Y,
                    tx = points[j].X,
                    ty = points[j].Y;

                // 点与多边形顶点重合或在多边形的边上
                if ((sx - px) * (px - tx) >= 0 && (sy - py) * (py - ty) >= 0 && (px - sx) * (ty - sy) == (py - sy) * (tx - sx))
                {
                    return true;
                }

                // 点与相邻顶点连线的夹角
                var angle = System.Math.Atan2(sy - py, sx - px) - System.Math.Atan2(ty - py, tx - px);

                // 确保夹角不超出取值范围（-π 到 π）
                if (angle >= System.Math.PI)
                {
                    angle = angle - System.Math.PI * 2;
                }
                else if (angle <= -System.Math.PI)
                {
                    angle = angle + System.Math.PI * 2;
                }

                sum += angle;
            }

            // 计算回转数并判断点和多边形的几何关系
            return System.Math.Round(sum / System.Math.PI) != 0;
        }

    }
}
